package demo2;

public class Solution {
    class Node {
        int value;
        Node next;

        public Node(int data, Node node) {
            this.value = data;
            this.next = node;
        }
    }

    public int iceBreakingGame(int num, int target) {
        // 边界条件：num <= 1 时，直接返回 0（无淘汰必要）
        if (num <= 1) {
            return 0;
        }

        // 1. 构建循环链表（确保 cur 全程非 null）
        Node head = new Node(0, null); // 直接创建头节点（编号 0）
        Node cur = head;
        for (int i = 1; i < num; i++) { // 从 1 开始创建其他节点（避免重复判断 head）
            Node node = new Node(i, null);
            cur.next = node;
            cur = node;
        }
        cur.next = head; // 首尾相连，形成循环
        cur = head;      // cur 回到头节点，准备淘汰

        // 2. 模拟淘汰过程（修复 prev 空指针问题）
        Node prev = null;
        while (cur.next != cur) { // 只剩 1 个节点时退出
            // 移动 target-1 次，找到第 target 位节点（核心逻辑）
            for (int i = 1; i < target; i++) {
                prev = cur;
                cur = cur.next;
            }

            // 处理 prev 为 null 的情况（target=1 时触发）
            if (prev == null) {
                // 此时要淘汰的是头节点 cur，需要先找到尾节点（prev 指向尾节点）
                Node tail = cur;
                while (tail.next != cur) {
                    tail = tail.next;
                }
                prev = tail;
            }

            // 删除当前节点（淘汰）：prev 指向 cur 的下一个节点
            prev.next = cur.next;
            // cur 指向淘汰节点的下一个，准备下一轮计数
            cur = prev.next;
        }

        return cur.value;
    }
}